Both category theory and graph theory study patterns based on diagrams consisting of nodes and edges. Despite this surface impression, there is in fact very little interaction between the scientific communities of category theorists and of graph theorists.
This article is a modest bridge, indicating that the category of graphs (in the usual graph-theorist’s sense – see for example Diestel) has some very nice properties.
By a simple graph, we mean a set whose elements are called vertices, together with a collection of 2-element subsets of ; these are called edges of the graph.
There are various ways of forming a category of simple graphs. Perhaps the most straightforward is to define a graph morphism to be a function between the vertex sets such that is an edge of whenever is an edge of .
Another option – and this is the one chosen for this article – starts by regarding a simple graph as carrying the same information as a set equipped with a symmetric reflexive relation . Indeed, such a relation determines (and is uniquely determined by) a simple graph where for given vertices , there is an edge between and in iff both and . We will write to mean .
Then, under the relational formulation, we define a morphism between simple graphs straightforwardly1 as a function that preserves the relevant structure, i.e., that implies . One reason for preferring this notion of morphism is that it allows, for example, consideration of arbitrary edge contractions of a simple graph as quotients in the category (cf. graph minor), something that is not possible under the prior notion of morphism.
Thus we will adopt the latter notion of morphism which takes reflexive symmetric relations as primary. The resulting category of simple graphs is denoted by .
Note that graphs and their morphisms can also be understood in functorial language, by regarding simple graphs as special types of presheaves, as follows. Let be the category of sets and and functions between them. Then a presheaf is given by sets and and maps
(source map),
(target map),
(reflexive map),
(symmetry map).
satisfying appropriate identities imposed by equations in . Simple graphs can then be regarded equivalently as such presheaves where the map
is a monomorphism. In that case, a morphism of simple graphs amounts to a natural transformation between such presheaves.
“Simple graph” as defined in the nLab (see graph) means that edges are 2-element subsets of , but of course that doesn’t preclude consideration of other types of graph. One option is to consider sets equipped with a collection of subsets of of cardinality either 1 or 2, i.e., allowing some but not necessarily all loops as edges. We don’t call those “simple graphs” (at graph they are called “loop graphs”), but nevertheless they form a respectable category under the straightforward notion of morphism (if is an edge of the domain, possibly with , then is an edge of the codomain). Chih and Scull use this category, which they refer to as , in their paper Homotopy in the Category of Graphs.
The category has very good properties. For example,
is a Grothendieck quasitopos. In particular, it is a regular category and even a logos, and is also regular. It is also -extensive.
(See also Adamek and Herrlich.) As above, let be the category of sets and and functions between them, and regard the category of simple graphs as a full subcategory of the presheaf topos . For this presheaf topos, there is just one nontrivial -dense sieve, namely the inclusion
(where is shorthand for and similarly for ) and so the category of -separated presheaves is equivalent to the category of presheaves such that the induced map
which is the source-target pairing , is monic. In other words, a simple graph in this language is exactly a separated presheaf. On the other hand, a Grothendieck quasitopos is, essentially by definition, the category of separated presheaves for a topology on a presheaf topos, in this case the -topology.
Being a quasitopos with small coproducts, it is -extensive provided that coproducts are disjoint. However, this is trivial to check (it even suffices to check, according to Elephant 2.6.5, that is a regular monomorphism, or that is a disjoint coproduct, which it obviously is).
Implicit in this proof is the way in which (for example) limits of simple graphs are calculated. Since is realized as a category of separated presheaves which is a reflective subcategory of all presheaves, limits in are calculated just as they are in the presheaf category , which is to say: they are computed objectwise, at the objects of .
For example, consider how to construct the equalizer of a pair of graph maps . For the vertex set of the equalizer (computing the equalizer at the object of ), one just takes the equalizer of the functions between the vertex sets of and . At the edge set level where we have maps : since there is at most one edge between two vertices, the maps must agree on provided and , so the equalizer graph is just the full or induced subgraph of given by the equalizer vertex set.
Moreover, every induced subgraph arises as an equalizer (consider the equalizer of the two embeddings of into the amalgamation , which at the vertex level agrees with ).
Of course this is elementary, but we get much more more: the quasitopos is also a locally cartesian closed category, and dependent products can also be read off directly from how they work for presheaves.
It is easy to describe monos and epis in . For, let be the underlying vertex-set forgetful functor.
The forgetful functor is faithful, in fact exhibits as a topological concrete category.
We omit the easy proof. Next we have two easy results:
reflects monos and epis (because is faithful).
preserves limits and colimits (because it has a left adjoint and a right adjoint ).
It follows that both preserves and reflects monos and epis. As a result, we can prove various simple exactness results in . For instance:
In , the pushout of any mono is a mono.
Suppose we have a pushout diagram in :
Since preserves both pushouts and monos, and since the pushout of a mono in is a mono, we have that is monic in . Since reflects monos, this means is monic in .
As already observed, there is a chain of adjoint functors . But in fact there is a fourth functor in the chain: has a left adjoint , the connected components functor. If is the simple graph consisting of two vertices with an edge between them, then there is a reflexive fork
and is formed as a reflexive coequalizer of the induced diagram:
, and preserves products.
preserves products because being a reflexive coequalizer, it is a sifted colimit of product-preserving functors. For graphs , there is a natural map which at the underlying vertex-set level sends a vertex to its connected component; if is any set, then a graph map must send any two vertices with an edge between them to the same point, and so factors as for a unique map , and this establishes the adjunction .
If are maps in , then their equalizer is given at the vertex level by
and at the edge level by ; in other words, if belong to and there is an edge between them in , then that edge lies in . To express this last condition, we say the subgraph is full (at the edge level).
Thus, is a regular mono in iff both is monic in and is full at the edge level (see Remark ).
The coequalizer of and , say , is given at the vertex level by
and at the edge level by taking the image of the composite , so that
Thus, is a regular epimorphism if it is surjective at both the vertex and edge levels.
The category of simple graphs has a ternary factorization system as follows: each morphism factors as
where
is a surjection between vertex-sets and at the edge level, i.e., is a regular epi;
induces an identity between vertex-sets (hence is jointly monic and epic?), but without necessarily being full at the edge level;
is given by an injection between vertex-sets and is full at the edge level, and (thus) is a regular mono.
The factorization of into followed by is the (regular epi)-mono factorization, while the factorization of into followed by is the epi-(regular mono) factorization. (The fact that regular monos are stable under pushout, used to ensure that the epi-(regular mono) factorization is an orthogonal factorization system, is true because , being a quasitopos, is a coregular category, meaning is regular.) Both factorizations coincide at the level of underlying functions between vertex sets, both being the usual epi-mono factorization.
In particular, we have the easy facts that
is a mono iff is a graph isomorphism: monos in are simple graph maps that are injective on vertices and edges,
is an epi iff is a graph isomorphism: epis in are simple graph maps that are surjective on vertices.
Graph theory suggests both full and wide subcategories of . See the category of simple graphs from a graph-theoretic perspective for more details.
The category has a natural numbers object; on abstract grounds this is formed by applying the reflection functor
to the natural numbers object in .
In other words, the usual notion of morphism between structures or models as in model theory. ↩
Last revised on September 11, 2019 at 10:39:16. See the history of this page for a list of all contributions to it.